package 剑指offer.demo5;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

//https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?
public class 最小的K个数 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        //合法性判断
        if (k > input.length || input.length == 0 || k == 0)
            return list;
        //优先级队列，默认优先级队列后升序排列
        PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
        for (int a : input
             ) {
            if (que.size() < k){
                que.offer(a);
            }else {
                if (a < que.peek()){
                    que.poll();
                    que.offer(a);
                }
            }
        }
        while (!que.isEmpty()){
            list.add(que.poll());
        }
        return list;
    }
}
